#include<iostream>
using namespace std;
int fib1(int n);
int fib2(int n);
int fib21(int n);


int main(){
    int n = 5;
    int arr[n];

    arr[0] = 0;
    arr[1] = 1;

    for (int i = 2; i < n; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }

    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << endl;

    }

    // return 0;

    cout<<"-----------------------"<<endl;

    cout<<fib1(0)<<endl;
    cout<<fib1(1)<<endl;
    cout<<fib1(2)<<endl;
    cout<<fib1(3)<<endl;
    cout<<fib1(4)<<endl;
    cout<<fib1(5)<<endl;

    cout<<"-----------------------"<<endl;


    cout<<fib2(0)<<endl;
    cout<<fib2(1)<<endl;
    cout<<fib2(2)<<endl;
    cout<<fib2(3)<<endl;
    cout<<fib2(4)<<endl;
    cout<<fib2(5)<<endl;

    cout<<"-----------------------"<<endl;
    // cout<<fib21(0)<<endl;
    // cout<<fib21(1)<<endl;
    // cout<<fib21(2)<<endl;
    // cout<<fib21(3)<<endl;
    // cout<<fib21(4)<<endl;
    cout<<fib21(5)<<endl;


}

int fib1(int n){
    if(n<0){
        cout<<"fib1 params n nedd >0"<<endl;
        return -1;
    }
    if(n<=1){
        return n;
    }else{
        return fib1(n-1)+fib1(n-2);
    }
}

int fib2(int n){
    if(n<0){
        cout<<"fib2 params n nedd >0"<<endl;
        return -1;
    }
    if(n==1||n==0){
        return n;
    }
    int pre=1;
    int cur=0;
    for (int i = 2; i <= n; i++){
        int tmp=pre+cur;
        cur=pre;
        pre=tmp;
    }
    return pre; 
}

int fib21(int n){
    if(n<0){
        cout<<"fib21 params n nedd >0"<<endl;
        return -1;
    }
    if(n==1||n==0){
        return n;
    }
    int tmp[n+1];
    tmp[0]=0;
    tmp[1]=1;
    for (int i = 2; i <=n; i++){
        tmp[i]=tmp[i-1]+tmp[i-2];
    }
    for (int i = 0; i <=n; i++)
    {
        std::cout <<to_string(i)+ " , "+ to_string(tmp[i]) << endl;
    }
    
    return tmp[n]; 
}